1884D - Counting Rhyme - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000013;
ll f[N];
ll ban[N];
ll s[N];
void solve(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)f[i]=s[i]=ban[i]=0;
    for(int i=1,x;i<=n;i++)cin>>x,f[x]++,ban[x]=1;
    for(int i=1;i<=n;i++)for(int j=i+i;j<=n;j+=i)ban[j]|=ban[i];
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)s[i]+=f[j];
    for(int i=1;i<=n;i++)s[i]=s[i]*(s[i]-1)/2;
    for(int i=n;i;i--)for(int j=i+i;j<=n;j+=i)s[i]-=s[j];
    ll ans=0;
    for(int i=1;i<=n;i++)if(!ban[i])(ans+=s[i]);
    cout<<ans<<'\n';
}
int main(){
    int T=1;
    cin>>T;
    while(T--)solve();
}